
export class ListNode<T>{
    public next: ListNode<T> | null;
    public prev: ListNode<T> | null;
    public data: T | undefined;
    public constructor(data: T | undefined = undefined) {
        this.next = this.prev = null;
        this.data = data;
    }
}

// 双向：是指每个ListNode的后驱指针next指向下一个ListNode，
//      每个ListNode的前驱指针prev指向前一个ListNode。
//      我们很容易地通过next和prev指针进行从前到后或者从后到前的双向遍历操作。

// 循环：我们通过List的头节点和最后一个节点可以了解到
//      头节点h的前驱指针指向最后一个节点（尾节点），
//      而最后一个节点（尾节点）的后驱指针next指向头节点h，从而首尾相连，形成一个闭环。

/**
 * 双向循环列表
 */
export class List<T>{

    /**游标卡尺的感觉 纯指针记录位置 */
    private _headNode: ListNode<T>;
    private _length: number;

    public constructor() {
        this._headNode = new ListNode<T>();
        this._headNode.next = this._headNode;
        this._headNode.prev = this._headNode;
        this._length = 0;
    }

    public empty(): boolean {
        //当头节点的next指针 指向 头节点本身时，说明是空链表
        return this._headNode.next === this._headNode;
    }

    public get length(): number {
        //如果当前list 的length为0,则说明是个空链表
        return this._length;
    }

    public begin(): ListNode<T> {
        if (this._headNode.next == null) {
            throw new Error('头节点的next指针必须不为null');
        }
        //若是链表不为空，则返回第一个节点
        //若是链表为空，next指向头节点本身，因此返回头节点
        //绝对不可能返回null值
        return this._headNode.next;
    }

    public end(): ListNode<T> {
        return this._headNode;
    }

    public contains(data: T): boolean {
        for (let link: ListNode<T> | null = this._headNode.next;
            link != null && link != this._headNode; link = link.next) {
            if (link !== null && link.data != undefined && link.data === link.data) {
                return true;
            }
        }
        return false;
    }

    public forNext(cb: (data: T) => void): void {
        for (let link: ListNode<T> | null = this._headNode.next;
            link != null && link != this._headNode; link = link.next) {
            if (link !== null && link.data != undefined) {
                cb(link.data);
            }
        }
    }

    public forPrev(cb: (data: T) => void): void {
        for (let link: ListNode<T> | null = this._headNode.prev;
            link != null && link != this._headNode; link = link.prev) {
            if (link !== null && link.data != undefined) {
                cb(link.data);
            }
        }
    }

    public insertBefore(node: ListNode<T>, data: T): ListNode<T> {

        let ret: ListNode<T> = new ListNode<T>(data);

        //设置新节点的后驱指针和前驱指针
        ret.next = node;
        ret.prev = node.prev;

        //设置参考节点的前后驱指针
        if (node.prev != null) {
            node.prev.next = ret;
        }
        node.prev = ret;
        this._length++;
        return ret;
    }

    public remove(node: ListNode<T>): void {

        let next = node.next;
        let prev = node.prev;

        if (prev != null) {
            prev.next = next;
        }

        if (next != null) {
            next.prev = prev;
        }

        this._length--;

    }

    public push(data: T): void {
        this.insertBefore(this.end(), data);
    }

    public pop(): T | undefined {
        let prev = this.end().prev;
        if (prev != null) {
            let ret = prev.data;
            this.remove(prev);
            return ret;
        }
        return undefined;
    }

    public push_front(data: T): void {
        this.insertBefore(this.begin(), data);
    }

    public pop_front(): T | undefined {
        let ret = this.begin().data;
        this.remove(this.begin());
        return ret;
    }

}